//
// (C) Copyright 2009 Irantha Suwandarathna (irantha@gmail.com)
// All rights reserved.
//

/* Copyright (c) 2001-2008, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


using System;
using System.Collections.Generic;
using System.Text;

namespace EffiProz.Core.Store
{
    /**
     * A chained bucket hash index implementation.
     *
     * hashTable and linkTable are arrays of signed integral types. This
     * implementation uses int as the type but short or byte can be used for
     * smaller index sizes (cardinality).
     *
     * hashTable[index] contains the pointer to the first node with
     * (index == hash modulo hashTable.Length) or -1 if there is no corresponding
     * node. linkTable[{0,newNodePointer}] (the range between 0 and newNodePointer)
     * contains either the pointer to the next node or -1 if there is no
     * such node. reclaimedNodeIndex contains a pointer to an element
     * of linkTable which is the first element _in the list of reclaimed nodes
     * (nodes no longer _in index) or -1 if there is no such node.
     *
     * elemenet at and above linkTable[newNodePointer] have never been used
     * as a node and their contents is not significant.
     *
     * @author fredt@users
     * @version 1.7.2
     * @since 1.7.2
     */
    public class HashIndex
    {

        public int[] hashTable;
        public int[] linkTable;
        public int newNodePointer;
        public int elementCount;
        public int reclaimedNodePointer = -1;
        public bool fixedSize;
        public bool modified;

        public HashIndex(int hashTableSize, int capacity, bool fixedSize)
        {

            if (capacity < hashTableSize)
            {
                capacity = hashTableSize;
            }
            reset(hashTableSize, capacity);

            this.fixedSize = fixedSize;
        }

        /**
         * Reset the structure with a new size as empty.
         *
         * @param hashTableSize
         * @param capacity
         */
        public void reset(int hashTableSize, int capacity)
        {

            int[] newHT = new int[hashTableSize];
            int[] newLT = new int[capacity];

            // allocate memory before assigning
            hashTable = newHT;
            linkTable = newLT;

            resetTables();
        }

        public void resetTables()
        {

            int to = hashTable.Length;
            int[] intArray = hashTable;

            while (--to >= 0)
            {
                intArray[to] = -1;
            }

            newNodePointer = 0;
            elementCount = 0;
            reclaimedNodePointer = -1;
            modified = false;
        }

        /**
         * Reset the index as empty.
         */
        public void clear()
        {

            int to = linkTable.Length;
            int[] intArray = linkTable;

            while (--to >= 0)
            {
                intArray[to] = 0;
            }

            resetTables();
        }

        /**
         * @param hash
         */
        public int getHashIndex(int hash)
        {
            return (hash & 0x7fffffff) % hashTable.Length;
        }

        /**
         * Return the array index for a hash.
         *
         * @param hash the hash value used for indexing
         * @return either -1 or the first node for this hash value
         */
        public int getLookup(int hash)
        {
            if (elementCount == 0)
            {
                return -1;
            }

            int index = (hash & 0x7fffffff) % hashTable.Length;

            return hashTable[index];
        }

        /**
         * This looks from a given node, so the parameter is always > -1.
         *
         * @param valid lookup node to look from
         * @return either -1 or the next node from this node
         */
        public int getNextLookup(int lookup)
        {
            return linkTable[lookup];
        }

        /**
         * Link a new node to the end of the linked for a hash index.
         *
         * @param index an index into hashTable
         * @param lastLookup either -1 or the node to which the new node will be linked
         * @return the new node
         */
        public int linkNode(int index, int lastLookup)
        {

            // get the first reclaimed slot
            int lookup = reclaimedNodePointer;

            if (lookup == -1)
            {
                lookup = newNodePointer++;
            }
            else
            {

                // reset the first reclaimed slot
                reclaimedNodePointer = linkTable[lookup];
            }

            // link the node
            if (lastLookup == -1)
            {
                hashTable[index] = lookup;
            }
            else
            {
                linkTable[lastLookup] = lookup;
            }

            linkTable[lookup] = -1;

            elementCount++;

            modified = true;
            return lookup;
        }

        /**
         * Unlink a node from a linked list and link into the reclaimed list.
         *
         * @param index an index into hashTable
         * @param lastLookup either -1 or the node to which the target node is linked
         * @param lookup the node to remove
         */
        public void unlinkNode(int index, int lastLookup, int lookup)
        {

            // unlink the node
            if (lastLookup == -1)
            {
                hashTable[index] = linkTable[lookup];
            }
            else
            {
                linkTable[lastLookup] = linkTable[lookup];
            }

            // add to reclaimed list
            linkTable[lookup] = reclaimedNodePointer;
            reclaimedNodePointer = lookup;

            elementCount--;
        }

        /**
         * Remove a node that has already been unlinked. This is not required
         * for index operations. It is used only when the row needs to be removed
         * from the data structures that store the actual indexed data and the
         * nodes need to be contiguous.
         *
         * @param lookup the node to remove
         * @return true if node found _in unlinked state
         */
        public bool removeEmptyNode(int lookup)
        {

            bool found = false;
            int lastLookup = -1;

            for (int i = reclaimedNodePointer; i >= 0;
                    lastLookup = i, i = linkTable[i])
            {
                if (i == lookup)
                {
                    if (lastLookup == -1)
                    {
                        reclaimedNodePointer = linkTable[lookup];
                    }
                    else
                    {
                        linkTable[lastLookup] = linkTable[lookup];
                    }

                    found = true;

                    break;
                }
            }

            if (!found)
            {
                return false;
            }

            for (int i = 0; i < newNodePointer; i++)
            {
                if (linkTable[i] > lookup)
                {
                    linkTable[i]--;
                }
            }

            Array.Copy(linkTable, lookup + 1, linkTable, lookup,
                             newNodePointer - lookup - 1);

            linkTable[newNodePointer - 1] = 0;

            newNodePointer--;

            for (int i = 0; i < hashTable.Length; i++)
            {
                if (hashTable[i] > lookup)
                {
                    hashTable[i]--;
                }
            }

            return true;
        }
    }
}